//===----------------------------------------------------------------------===//
//
//                         BusTub
//
// lock_manager.cpp
//
// Identification: src/concurrency/lock_manager.cpp
//
// Copyright (c) 2015-2019, Carnegie Mellon University Database Group
//
//===----------------------------------------------------------------------===//

#include "concurrency/lock_manager.h"
#include <algorithm>

#include "common/config.h"
#include "concurrency/transaction.h"
#include "concurrency/transaction_manager.h"

namespace bustub {
// slides_map 3,5,1,2,4,
//     S, X, I, IX, SIX
// S
// X
// I
// IX
// SIX
std::vector<std::vector<int>> LockManager::compatibility_matrix = {
    {1, 0, 1, 0, 0}, {0, 0, 0, 0, 0}, {1, 0, 1, 1, 1}, {0, 0, 1, 1, 0}, {0, 0, 1, 0, 0},
};
// // row:lock mode;col:isolation level
// std::vector<std::vector<int>> LockManager::isolation_level_matrix = {
// {1,0,1,0,0},
// {0,0,0,0,0},
// {0,0,1,0,0},
// };

// row:requested_lock_mode;col:curr_lock_mode
//    S, X, IS, IX, SIX
// S       1         1
// X
// IS
// IX
// SIX
//    *        S -> [X, SIX]

//             IS -> [S, X, IX, SIX]
//    *        IX -> [X, SIX]
//    *        SIX -> [X]
std::vector<std::vector<int>> LockManager::lock_upgrade_matrix = {
    {0, 1, 0, 0, 1}, {0, 0, 0, 0, 0}, {1, 1, 0, 1, 1}, {0, 1, 0, 0, 1}, {0, 1, 0, 0, 0},
};

auto LockManager::CanLockUpgrade(LockMode curr_lock_mode, LockMode requested_lock_mode) -> bool {
  // LOG_DEBUG("curr_lock_mode=%d, requested_lock_mode=%d", curr_lock_mode, requested_lock_mode);
  return lock_upgrade_matrix[static_cast<int>(curr_lock_mode)][static_cast<int>(requested_lock_mode)] != 0;
}

auto LockManager::GetCurTableLockMode(Transaction *txn, const table_oid_t &oid) -> int {
  int cur_lock_mode = -1;
  if (txn->IsTableSharedLocked(oid)) {
    cur_lock_mode = static_cast<int>(LockMode::SHARED);
  }
  if (txn->IsTableExclusiveLocked(oid)) {
    cur_lock_mode = static_cast<int>(LockMode::EXCLUSIVE);
  }
  if (txn->IsTableIntentionSharedLocked(oid)) {
    cur_lock_mode = static_cast<int>(LockMode::INTENTION_SHARED);
  }
  if (txn->IsTableIntentionExclusiveLocked(oid)) {
    cur_lock_mode = static_cast<int>(LockMode::INTENTION_EXCLUSIVE);
  }
  if (txn->IsTableSharedIntentionExclusiveLocked(oid)) {
    cur_lock_mode = static_cast<int>(LockMode::SHARED_INTENTION_EXCLUSIVE);
  }
  return cur_lock_mode;
}

auto LockManager::GetCurRowLockMode(Transaction *txn, const table_oid_t &oid, const RID &rid) -> int {
  int cur_lock_mode = -1;
  if (txn->IsRowExclusiveLocked(oid, rid)) {
    cur_lock_mode = static_cast<int>(LockMode::EXCLUSIVE);
  }
  if (txn->IsRowSharedLocked(oid, rid)) {
    cur_lock_mode = static_cast<int>(LockMode::SHARED);
  }
  return cur_lock_mode;
}

auto LockManager::LockTable(Transaction *txn, LockMode lock_mode, const table_oid_t &oid) -> bool {
  LOG_DEBUG("txnid=%d, lock_mode=%d, oid=%d", txn->GetTransactionId(), lock_mode, oid);
  // BUSTUB_ASSERT((int)lock_mode != 2, "can not IS");

  // ISOLATION LEVEL:
  if (!CanTxnTakeLock(txn, lock_mode)) {
    return false;
  }

  // CHECK LOCK UPGRADE:
  auto cur_lock_mode = GetCurTableLockMode(txn, oid);
  if (static_cast<int>(lock_mode) == cur_lock_mode) {
    return true;
  }
  if (cur_lock_mode != -1) {
    // LOG_DEBUG("cur_lock_mode=%d, lock_mode=%d", cur_lock_mode, lock_mode);
    bool can_lock_upgrade = CanLockUpgrade(static_cast<LockMode>(cur_lock_mode), lock_mode);
    LOG_DEBUG("can_lock_upgrade=%d", can_lock_upgrade);
    if (!can_lock_upgrade) {
      txn->SetState(TransactionState::ABORTED);
      throw TransactionAbortException(txn->GetTransactionId(), AbortReason::INCOMPATIBLE_UPGRADE);
    }
  }

  // txn->SetState(TransactionState::GROWING);

  std::unique_lock<std::mutex> table_guard(table_lock_map_latch_);
  // 该表无锁
  if (table_lock_map_.count(oid) == 0) {
    auto lock_request_queue = std::make_shared<LockRequestQueue>();
    lock_request_queue->request_queue_.emplace_back(
        std::make_shared<LockRequest>(txn->GetTransactionId(), lock_mode, oid));
    table_lock_map_[oid] = lock_request_queue;
    lock_request_queue->request_queue_.back()->granted_ = true;
    InsertTableLockSet(txn, lock_mode, oid);
    LOG_DEBUG("txnid=%d, lock_mode=%d, oid=%d", txn->GetTransactionId(), lock_mode, oid);
    return true;
  }

  // 该表有锁
  // 加队列latch，释放table_latch
  auto lock_request_queue = table_lock_map_[oid];
  std::unique_lock<std::mutex> queue_guard(lock_request_queue->latch_);
  table_guard.unlock();
  std::list<std::shared_ptr<LockRequest>> &request_queue = lock_request_queue->request_queue_;

  // 事务之前没加过锁，直接往队列后加
  if (cur_lock_mode == -1) {
    request_queue.emplace_back(std::make_shared<LockRequest>(txn->GetTransactionId(), lock_mode, oid));
  } else {
    // 升级
    if (lock_request_queue->upgrading_ != INVALID_TXN_ID) {
      txn->SetState(TransactionState::ABORTED);
      throw TransactionAbortException(txn->GetTransactionId(), AbortReason::UPGRADE_CONFLICT);
    }
    lock_request_queue->upgrading_ = txn->GetTransactionId();
    // 正在升级的锁请求应优先于同一资源上的其他等待锁定请求。
    // 删除旧lock_mode
    request_queue.remove_if(
        [&](const std::shared_ptr<LockRequest> &item) { return item->txn_id_ == txn->GetTransactionId(); });
    // 删除事务中的记录
    EraseTableLockSet(txn, static_cast<LockMode>(cur_lock_mode), oid);

    // 插入新lock_mode
    // 将一条新的记录插入在队列最前面一条未授予的记录之前
    auto insert_into = std::find_if(request_queue.begin(), request_queue.end(),
                                    [](const std::shared_ptr<LockRequest> &item) { return !item->granted_; });
    request_queue.insert(insert_into, std::make_shared<LockRequest>(txn->GetTransactionId(), lock_mode, oid));
  }
  // 检查兼容性，等待在条件变量上GrantNewLocksIfPossible?
  LOG_DEBUG("txn=%d wait table", txn->GetTransactionId());
  while (!Grant(txn, lock_mode, request_queue)) {
    lock_request_queue->cv_.wait(queue_guard);
    if (txn->GetState() == TransactionState::ABORTED) {
      break;
    }
  }

  LOG_DEBUG("%d wake up, state=%d", txn->GetTransactionId(), txn->GetState());

  // 醒来后再做一个事务状态判断
  if (txn->GetState() != TransactionState::ABORTED) {
    InsertTableLockSet(txn, lock_mode, oid);
    lock_request_queue->upgrading_ = INVALID_TXN_ID;
    return true;
  }
  lock_request_queue->cv_.notify_all();
  request_queue.remove_if(
      [&](const std::shared_ptr<LockRequest> &item) { return item->txn_id_ == txn->GetTransactionId(); });
  return false;
}

void LockManager::InsertTableLockSet(Transaction *txn, LockMode lock_mode, const table_oid_t &oid) {
  switch (lock_mode) {
    case LockMode::SHARED:
      txn->GetSharedTableLockSet()->insert(oid);
      break;
    case LockMode::EXCLUSIVE:
      txn->GetExclusiveTableLockSet()->insert(oid);
      break;
    case LockMode::INTENTION_SHARED:
      txn->GetIntentionSharedTableLockSet()->insert(oid);
      break;
    case LockMode::INTENTION_EXCLUSIVE:
      txn->GetIntentionExclusiveTableLockSet()->insert(oid);
      break;
    case LockMode::SHARED_INTENTION_EXCLUSIVE:
      txn->GetSharedIntentionExclusiveTableLockSet()->insert(oid);
      break;
    default:
      break;
  }
}

void LockManager::InsertRowLockSet(Transaction *txn, LockMode lock_mode, const table_oid_t &oid, const RID &rid) {
  LOG_DEBUG("txnid=%d, lock_mode=%d, oid=%d, rid=%s", txn->GetTransactionId(), lock_mode, oid, rid.ToString().c_str());
  switch (lock_mode) {
    case LockMode::SHARED:
      (*txn->GetSharedRowLockSet())[oid].emplace(rid);
      break;
    case LockMode::EXCLUSIVE:
      (*txn->GetExclusiveRowLockSet())[oid].emplace(rid);
      break;
    default:
      break;
  }
}

void LockManager::EraseRowLockSet(Transaction *txn, LockMode lock_mode, const table_oid_t &oid, const RID &rid) {
  LOG_DEBUG("txnid=%d, lock_mode=%d, oid=%d, rid=%s", txn->GetTransactionId(), lock_mode, oid, rid.ToString().c_str());
  switch (lock_mode) {
    case LockMode::SHARED:
      (*txn->GetSharedRowLockSet())[oid].erase(rid);
      break;
    case LockMode::EXCLUSIVE:
      (*txn->GetExclusiveRowLockSet())[oid].erase(rid);
      break;
    default:
      break;
  }
}

void LockManager::EraseTableLockSet(Transaction *txn, LockMode lock_mode, const table_oid_t &oid) {
  switch (lock_mode) {
    case LockMode::SHARED:
      txn->GetSharedTableLockSet()->erase(oid);
      break;
    case LockMode::EXCLUSIVE:
      txn->GetExclusiveTableLockSet()->erase(oid);
      break;
    case LockMode::INTENTION_SHARED:
      txn->GetIntentionSharedTableLockSet()->erase(oid);
      break;
    case LockMode::INTENTION_EXCLUSIVE:
      txn->GetIntentionExclusiveTableLockSet()->erase(oid);
      break;
    case LockMode::SHARED_INTENTION_EXCLUSIVE:
      txn->GetSharedIntentionExclusiveTableLockSet()->erase(oid);
      break;
    default:
      break;
  }
}

auto LockManager::CanTxnTakeLock(Transaction *txn, LockMode lock_mode) -> bool {
  IsolationLevel il = txn->GetIsolationLevel();
  TransactionState state = txn->GetState();
  LOG_DEBUG("IsolationLevel=%d", il);
  if (state == TransactionState::ABORTED) {
    return false;
  }
  if (il == IsolationLevel::READ_UNCOMMITTED) {
    if (state != TransactionState::SHRINKING) {
      if (lock_mode == LockMode::EXCLUSIVE || lock_mode == LockMode::INTENTION_EXCLUSIVE) {
        return true;
      }
      txn->SetState(TransactionState::ABORTED);
      throw TransactionAbortException(txn->GetTransactionId(), AbortReason::LOCK_SHARED_ON_READ_UNCOMMITTED);
    }
    if (state == TransactionState::SHRINKING) {
      txn->SetState(TransactionState::ABORTED);
      throw TransactionAbortException(txn->GetTransactionId(), AbortReason::LOCK_ON_SHRINKING);
    }
  }
  if (il == IsolationLevel::REPEATABLE_READ) {
    if (state != TransactionState::SHRINKING) {
      return true;
    }
    if (state == TransactionState::SHRINKING) {
      txn->SetState(TransactionState::ABORTED);
      throw TransactionAbortException(txn->GetTransactionId(), AbortReason::LOCK_ON_SHRINKING);
    }
  }
  if (il == IsolationLevel::READ_COMMITTED) {
    if (state != TransactionState::SHRINKING) {
      return true;
    }
    if (state == TransactionState::SHRINKING) {
      if (lock_mode == LockMode::INTENTION_SHARED || lock_mode == LockMode::SHARED) {
        return true;
      }
      txn->SetState(TransactionState::ABORTED);
      throw TransactionAbortException(txn->GetTransactionId(), AbortReason::LOCK_ON_SHRINKING);
    }
  }
  LOG_DEBUG("IsolationLevel=%d, state=%d, lock_mode=%d", il, state, lock_mode);
  // BUSTUB_ASSERT(0, "IsolationLevel not Support");
  // txn->SetState(TransactionState::ABORTED);
  return false;
}

auto LockManager::UnlockTable(Transaction *txn, const table_oid_t &oid) -> bool {
  LOG_DEBUG("txnid=%d, oid=%d", txn->GetTransactionId(), oid);

  // check hold on table lock
  auto cur_lock_mode = GetCurTableLockMode(txn, oid);
  if (cur_lock_mode == -1) {
    LOG_DEBUG("txnid=%d, oid=%d", txn->GetTransactionId(), oid);
    txn->SetState(TransactionState::ABORTED);
    throw TransactionAbortException(txn->GetTransactionId(), AbortReason::ATTEMPTED_UNLOCK_BUT_NO_LOCK_HELD);
  }

  // check hold on row lock
  if (!(*txn->GetSharedRowLockSet())[oid].empty() || !(*txn->GetExclusiveRowLockSet())[oid].empty()) {
    LOG_DEBUG("txnid=%d, oid=%d", txn->GetTransactionId(), oid);
    txn->SetState(TransactionState::ABORTED);
    throw TransactionAbortException(txn->GetTransactionId(), AbortReason::TABLE_UNLOCKED_BEFORE_UNLOCKING_ROWS);
  }

  // update lock state
  IsolationLevel il = txn->GetIsolationLevel();
  if (il == IsolationLevel::REPEATABLE_READ &&
      (cur_lock_mode == static_cast<int>(LockMode::SHARED) || cur_lock_mode == static_cast<int>(LockMode::EXCLUSIVE))) {
    txn->SetState(TransactionState::SHRINKING);
  }

  if (il == IsolationLevel::READ_COMMITTED && cur_lock_mode == static_cast<int>(LockMode::EXCLUSIVE)) {
    txn->SetState(TransactionState::SHRINKING);
  }

  if (il == IsolationLevel::READ_UNCOMMITTED && cur_lock_mode == static_cast<int>(LockMode::EXCLUSIVE)) {
    txn->SetState(TransactionState::SHRINKING);
  }

  std::unique_lock<std::mutex> table_guard(table_lock_map_latch_);
  // 加队列latch，释放table_latch
  auto lock_request_queue = table_lock_map_[oid];
  std::unique_lock<std::mutex> queue_guard(lock_request_queue->latch_);
  table_guard.unlock();
  std::list<std::shared_ptr<LockRequest>> &request_queue = lock_request_queue->request_queue_;
  request_queue.remove_if(
      [&](const std::shared_ptr<LockRequest> &item) { return item->txn_id_ == txn->GetTransactionId(); });

  lock_request_queue->cv_.notify_all();
  queue_guard.unlock();
  // SHRINKING

  // 删除事务中的记录
  EraseTableLockSet(txn, static_cast<LockMode>(cur_lock_mode), oid);
  return true;
}

auto LockManager::LockRow(Transaction *txn, LockMode lock_mode, const table_oid_t &oid, const RID &rid) -> bool {
  LOG_DEBUG("txnid=%d, lock_mode=%d, oid=%d, rid=%s", txn->GetTransactionId(), lock_mode, oid, rid.ToString().c_str());
  if (lock_mode != LockMode::SHARED && lock_mode != LockMode::EXCLUSIVE) {
    txn->SetState(TransactionState::ABORTED);
    throw TransactionAbortException(txn->GetTransactionId(), AbortReason::ATTEMPTED_INTENTION_LOCK_ON_ROW);
  }

  // ISOLATION LEVEL:
  if (!CanTxnTakeLock(txn, lock_mode)) {
    return false;
  }

  // CHECK TABLE LOCK PRESENT
  auto cur_table_lock_mode = GetCurTableLockMode(txn, oid);
  LOG_DEBUG("cur_table_lock_mode=%d", cur_table_lock_mode);
  if (lock_mode == LockMode::EXCLUSIVE && cur_table_lock_mode != static_cast<int>(LockMode::EXCLUSIVE) &&
      cur_table_lock_mode != static_cast<int>(LockMode::INTENTION_EXCLUSIVE) &&
      cur_table_lock_mode != static_cast<int>(LockMode::SHARED_INTENTION_EXCLUSIVE)) {
    txn->SetState(TransactionState::ABORTED);
    throw TransactionAbortException(txn->GetTransactionId(), AbortReason::TABLE_LOCK_NOT_PRESENT);
  }
  // 行锁上共享锁，表锁确保有就行
  if (lock_mode == LockMode::SHARED && cur_table_lock_mode == -1) {
    txn->SetState(TransactionState::ABORTED);
    throw TransactionAbortException(txn->GetTransactionId(), AbortReason::TABLE_LOCK_NOT_PRESENT);
  }

  // CHECK LOCK UPGRADE:
  auto cur_lock_mode = GetCurRowLockMode(txn, oid, rid);
  if (static_cast<int>(lock_mode) == cur_lock_mode) {
    return true;
  }
  if (cur_lock_mode != -1) {
    bool can_lock_upgrade = CanLockUpgrade(static_cast<LockMode>(cur_lock_mode), lock_mode);
    if (!can_lock_upgrade) {
      txn->SetState(TransactionState::ABORTED);
      throw TransactionAbortException(txn->GetTransactionId(), AbortReason::INCOMPATIBLE_UPGRADE);
    }
  }

  std::unique_lock<std::mutex> row_guard(row_lock_map_latch_);
  // 该行无锁
  if (row_lock_map_.count(rid) == 0) {
    auto lock_request_queue = std::make_shared<LockRequestQueue>();
    lock_request_queue->request_queue_.emplace_back(
        std::make_shared<LockRequest>(txn->GetTransactionId(), lock_mode, oid, rid));
    row_lock_map_[rid] = lock_request_queue;
    lock_request_queue->request_queue_.back()->granted_ = true;
    InsertRowLockSet(txn, lock_mode, oid, rid);
    return true;
  }

  // txn->SetState(TransactionState::GROWING);

  // 该行有锁
  // 加队列latch，释放table_latch
  auto lock_request_queue = row_lock_map_[rid];
  std::unique_lock<std::mutex> queue_guard(lock_request_queue->latch_);
  row_guard.unlock();
  std::list<std::shared_ptr<LockRequest>> &request_queue = lock_request_queue->request_queue_;

  // 事务之前没加过锁，直接往队列后加
  if (cur_lock_mode == -1) {
    request_queue.emplace_back(std::make_shared<LockRequest>(txn->GetTransactionId(), lock_mode, oid, rid));
    LOG_DEBUG("cur_lock_mode=%d", cur_lock_mode);
  } else {
    // 升级
    if (lock_request_queue->upgrading_ != INVALID_TXN_ID) {
      txn->SetState(TransactionState::ABORTED);
      throw TransactionAbortException(txn->GetTransactionId(), AbortReason::UPGRADE_CONFLICT);
    }
    lock_request_queue->upgrading_ = txn->GetTransactionId();

    // 正在升级的锁请求应优先于同一资源上的其他等待锁定请求。
    // 删除旧lock_mode
    request_queue.remove_if(
        [&](const std::shared_ptr<LockRequest> &item) { return item->txn_id_ == txn->GetTransactionId(); });
    // 删除事务中的记录
    EraseRowLockSet(txn, static_cast<LockMode>(cur_lock_mode), oid, rid);

    // 插入新lock_mode
    // 将一条新的记录插入在队列最前面一条未授予的记录之前
    auto insert_into = std::find_if(request_queue.begin(), request_queue.end(),
                                    [](const std::shared_ptr<LockRequest> &item) { return !item->granted_; });
    request_queue.insert(insert_into, std::make_shared<LockRequest>(txn->GetTransactionId(), lock_mode, oid, rid));
  }
  // 检查兼容性，等待在条件变量上GrantNewLocksIfPossible?
  LOG_DEBUG("%d wait row", txn->GetTransactionId());
  // bool cond = false;
  while (!Grant(txn, lock_mode, request_queue)) {
    lock_request_queue->cv_.wait(queue_guard);
    if (txn->GetState() == TransactionState::ABORTED) {
      break;
    }
  }

  LOG_DEBUG("%d wake up, state=%d", txn->GetTransactionId(), txn->GetState());

  // 如果唤醒后事务状态不变(可能被Abort而改变状态),插入lockset
  if (txn->GetState() != TransactionState::ABORTED) {
    InsertRowLockSet(txn, lock_mode, oid, rid);
    lock_request_queue->upgrading_ = INVALID_TXN_ID;
    return true;
  }

  lock_request_queue->cv_.notify_all();

  // 否则在队列中删除此事务
  request_queue.remove_if(
      [&](const std::shared_ptr<LockRequest> &item) { return item->txn_id_ == txn->GetTransactionId(); });
  return false;
  // 拿到锁后要再通知其他事务一下，因为自己可能是队列中靠前的元素，而后被唤醒，
  // 而靠后的元素先被唤醒后，发现自己前面的事务未授予锁，继续睡眠，因此需要前面那个
  // 事务加锁结束(不一定成功)后再次唤醒自己
  // lock_request_queue->cv_.notify_all();
}

auto LockManager::Grant(Transaction *txn, LockMode lock_mode,
                        const std::list<std::shared_ptr<LockRequest>> &request_queue) -> bool {
  // 找到事务自己在队列中的位置
  auto self_it = std::find_if(
      request_queue.rbegin(), request_queue.rend(),
      [txn](const std::shared_ptr<LockRequest> &item) { return item->txn_id_ == txn->GetTransactionId(); });
  // std::cout << "it=" << (*self_it)->txn_id_ << " " << static_cast<int>((*self_it)->lock_mode_) << " "
  //           << (*self_it)->oid_ << " " << (*self_it)->rid_ << " " << (*self_it)->granted_ << std::endl;
  // auto next_it = self_it;
  // 被唤醒后和排在自己前面的事务对比，看是否兼容
  // next_it++;
  bool cond = true;
  for (auto comp_it = self_it; comp_it != request_queue.rend(); comp_it++) {
    // auto comp_txn = txn_manager_->GetTransaction((*comp_it)->txn_id_);
    // if (comp_txn->GetState() == TransactionState::ABORTED) {
    //   continue;
    // }
    auto next_it = comp_it;
    next_it++;
    for (auto it = next_it; it != request_queue.rend(); it++) {
      // auto it_txn_state = txn_manager_->GetTransaction((*it)->txn_id_)->GetState();
      // if (it_txn_state == TransactionState::ABORTED) {
      //   continue;
      // }
      if (!AreLocksCompatible((*comp_it)->lock_mode_, (*it)->lock_mode_)) {
        // LOG_DEBUG("--");
        cond = false;
      }
    }
  }
  // 如果唤醒后事务状态不变(可能被Abort而改变状态),授予
  if (txn->GetState() == TransactionState::GROWING && cond) {
    (*self_it)->granted_ = true;
  }
  return cond;
}

auto LockManager::UnlockRow(Transaction *txn, const table_oid_t &oid, const RID &rid, bool force) -> bool {
  LOG_DEBUG("txnid=%d, oid=%d, rid=%s", txn->GetTransactionId(), oid, rid.ToString().c_str());

  // check hold on row lock
  auto cur_lock_mode = GetCurRowLockMode(txn, oid, rid);
  LOG_DEBUG("cur_lock_mode=%d", cur_lock_mode);
  if (cur_lock_mode == -1) {
    txn->SetState(TransactionState::ABORTED);
    throw TransactionAbortException(txn->GetTransactionId(), AbortReason::ATTEMPTED_UNLOCK_BUT_NO_LOCK_HELD);
  }

  // ISOLATION LEVEL:
  IsolationLevel il = txn->GetIsolationLevel();

  if (!force && il == IsolationLevel::REPEATABLE_READ &&
      (cur_lock_mode == static_cast<int>(LockMode::SHARED) || cur_lock_mode == static_cast<int>(LockMode::EXCLUSIVE))) {
    txn->SetState(TransactionState::SHRINKING);
  }

  if (!force && il == IsolationLevel::READ_COMMITTED && cur_lock_mode == static_cast<int>(LockMode::EXCLUSIVE)) {
    txn->SetState(TransactionState::SHRINKING);
  }

  if (!force && il == IsolationLevel::READ_UNCOMMITTED && cur_lock_mode == static_cast<int>(LockMode::EXCLUSIVE)) {
    txn->SetState(TransactionState::SHRINKING);
  }

  std::unique_lock<std::mutex> row_guard(row_lock_map_latch_);
  // 加队列latch，释放row_latch
  auto lock_request_queue = row_lock_map_[rid];
  std::unique_lock<std::mutex> queue_guard(lock_request_queue->latch_);
  row_guard.unlock();
  std::list<std::shared_ptr<LockRequest>> &request_queue = lock_request_queue->request_queue_;
  request_queue.remove_if(
      [&](const std::shared_ptr<LockRequest> &item) { return item->txn_id_ == txn->GetTransactionId(); });

  lock_request_queue->cv_.notify_all();
  queue_guard.unlock();
  // SHRINKING

  // 删除事务中的记录
  EraseRowLockSet(txn, static_cast<LockMode>(cur_lock_mode), oid, rid);
  return true;
}

auto LockManager::AreLocksCompatible(LockMode l1, LockMode l2) -> bool {
  return LockManager::compatibility_matrix[static_cast<int>(l1)][static_cast<int>(l2)] != 0;
}

auto LockManager::UpgradeLockTable(Transaction *txn, LockMode lock_mode, const table_oid_t &oid) -> bool {
  // std::list<std::shared_ptr<LockRequest>>& request_queue = lock_request_queue->request_queue_;
  return true;
}

void LockManager::UnlockAll() {
  // You probably want to unlock all table and txn locks here.
}

void LockManager::AddEdge(txn_id_t t1, txn_id_t t2) {
  // std::unique_lock<std::mutex> waits_for_guard(waits_for_latch_);
  waits_for_[t1].emplace_back(t2);
  edges_.emplace_back(t1, t2);
  LOG_DEBUG("%d--->%d", t1, t2);
}

void LockManager::RemoveEdge(txn_id_t t1, txn_id_t t2) {
  // std::unique_lock<std::mutex> waits_for_guard(waits_for_latch_);
  LOG_DEBUG("waits_for_[t1]:%ld", waits_for_[t1].size());
  auto &waits_for_txns = waits_for_[t1];

  waits_for_txns.erase(
      std::remove_if(waits_for_txns.begin(), waits_for_txns.end(), [t2](const txn_id_t &t) { return t == t2; }),
      waits_for_txns.end());
  edges_.erase(std::remove_if(edges_.begin(), edges_.end(),
                              [t1, t2](const std::pair<txn_id_t, txn_id_t> &pair) {
                                return pair.first == t1 && pair.second == t2;
                              }),
               edges_.end());

  waits_for_txns.size();

  LOG_DEBUG("waits_for_txns_size:%ld", waits_for_txns.size());
  LOG_DEBUG("waits_for_[t1]:%ld", waits_for_[t1].size());
  LOG_DEBUG("%d--->%d", t1, t2);
}

auto LockManager::HasCycle(txn_id_t *txn_id) -> bool {
  std::vector<txn_id_t> path;
  std::unordered_set<txn_id_t> on_path;
  std::unordered_set<txn_id_t> visited;
  std::sort(edges_.begin(), edges_.end());
  for (auto &&item : edges_) {
    if (visited.find(item.first) == visited.end() && FindCycle(item.first, path, on_path, visited, txn_id)) {
      for (int i : path) {
        LOG_DEBUG("abort_txn_id=%d", i);
      }

      return true;
    }
  }

  return false;
}

auto LockManager::GetEdgeList() -> std::vector<std::pair<txn_id_t, txn_id_t>> {
  // std::vector<std::pair<txn_id_t, txn_id_t>> edges(0);
  return edges_;
}

auto LockManager::BuildGrah(std::list<std::shared_ptr<LockRequest>> &request_queue) -> void {
  auto t1 = request_queue.begin();
  while (t1 != request_queue.end()) {
    auto t2 = t1;
    t2++;
    for (; t2 != request_queue.end(); t2++) {
      if (!AreLocksCompatible((*t1)->lock_mode_, (*t2)->lock_mode_)) {
        AddEdge((*t1)->txn_id_, (*t2)->txn_id_);
      }
    }
    t1++;
  }
}

auto LockManager::FindCycle(txn_id_t source_txn, std::vector<txn_id_t> &path, std::unordered_set<txn_id_t> &on_path,
                            std::unordered_set<txn_id_t> &visited, txn_id_t *abort_txn_id) -> bool {
  if (visited.find(source_txn) == visited.end()) {
    visited.emplace(source_txn);
    on_path.emplace(source_txn);
    path.emplace_back(source_txn);
    for (int &it : waits_for_[source_txn]) {
      if (visited.find(it) == visited.end() && FindCycle(it, path, on_path, visited, abort_txn_id)) {
        std::sort(path.begin(), path.end());
        *abort_txn_id = path.back();
        return true;
      }
      if (on_path.find(it) != on_path.end()) {
        std::sort(path.begin(), path.end());
        *abort_txn_id = path.back();
        return true;
      }
    }
  }
  on_path.erase(source_txn);
  path.pop_back();
  return false;
}
void LockManager::RunCycleDetection() {
  while (enable_cycle_detection_) {
    std::this_thread::sleep_for(cycle_detection_interval);
    bool has_sycle = false;
    // build graph
    waits_for_.clear();
    edges_.clear();
    std::unique_lock<std::mutex> table_guard(table_lock_map_latch_);
    std::unique_lock<std::mutex> row_guard(row_lock_map_latch_);

    for (auto &&pair : table_lock_map_) {
      BuildGrah(pair.second->request_queue_);
    }
    for (auto &&pair : row_lock_map_) {
      BuildGrah(pair.second->request_queue_);
    }
    do {
      // has cycle
      txn_id_t txn_id;
      has_sycle = HasCycle(&txn_id);
      // LOG_DEBUG("HasCycle:%d", has_sycle);
      if (has_sycle) {
        auto txn = txn_manager_->GetTransaction(txn_id);
        txn->SetState(TransactionState::ABORTED);
        // find request_queue
        for (auto &&pair : table_lock_map_) {
          auto &request_queue = pair.second->request_queue_;
          auto it = std::find_if(request_queue.begin(), request_queue.end(),
                                 [txn_id](const std::shared_ptr<LockRequest> &req) { return txn_id == req->txn_id_; });
          if (it != request_queue.end()) {
            LOG_DEBUG("find txn:%d", (*it)->txn_id_);
            pair.second->cv_.notify_all();
          }
        }
        for (auto &&pair : row_lock_map_) {
          auto &request_queue = pair.second->request_queue_;
          auto it = std::find_if(request_queue.begin(), request_queue.end(),
                                 [txn_id](const std::shared_ptr<LockRequest> &req) { return txn_id == req->txn_id_; });
          if (it != request_queue.end()) {
            LOG_DEBUG("find txn:%d", (*it)->txn_id_);
            pair.second->cv_.notify_all();
          }
        }
        // RemoveEdge
        waits_for_.erase(txn_id);
        for (auto &&vetex : waits_for_) {
          auto &waits_for_txns = vetex.second;
          waits_for_txns.erase(std::remove_if(waits_for_txns.begin(), waits_for_txns.end(),
                                              [txn_id](const txn_id_t &t) { return t == txn_id; }),
                               waits_for_txns.end());
        }

        edges_.erase(std::remove_if(edges_.begin(), edges_.end(),
                                    [txn_id](const std::pair<txn_id_t, txn_id_t> &pair) {
                                      return pair.first == txn_id || pair.second == txn_id;
                                    }),
                     edges_.end());
      }
    } while (has_sycle);
  }
}

}  // namespace bustub
